Numerous applications ranging from e-commerce, government records, on-line education and libraries, as well as web-based services in general, rely on databases. Databases are a class of applications that manipulate large amounts of stored data. Such massive compilation of data is typically stored as tables. Conceptually, tables are a collection of rows and columns with each row containing a record and the columns determining what types of values populate a record. As the number of records proliferates, the size of such tables quickly grows larger and manipulation steps such as searches or queries that scan the whole table to retrieve a subset of the data matching a certain criteria or pattern become inefficient to the point of impracticality. The source of the inefficiency is the exhaustive inspection of each record in the table that is conducted in a search of query in order to determine whether a record matches desired criteria.
To mitigate the effects of exhaustive inspection, most database designs build and exploit indexes. Such indexes are typically sorted and contain a subset of the original record with a pointer to the corresponding record in the table. In this manner, queries that inspect an index are efficient, and practical, since they deal with a smaller set of data. Yet, the tradeoff of employing indexes for improved query performance is the degradation of the performance of inserts/updates to a table. The degradation arises from the fact that whenever a table is updated, the related indexes associated with the table required to be updated as well in order to present a consistent view to any queries that the database might handle. Such degradation remains a challenge to database designers and an obstacle to exploiting light-weight indexation for efficiently resolving insert/update requests.